#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <utility>
#include <algorithm>
#include <vector>

#define MIN_N 1
#define MAX_N 1000

#define MIN_M 1
#define MAX_M 20000

#define MIN_Q 1
#define MAX_Q 20000

#define MIN_V 0
#define MAX_V 2000000000

#define CASES 10

int gen_int(int minv, int maxv)
{
    int k = ((rand() << 16) ^ rand()) & 0x7fffffff;
    return minv + k % (maxv - minv + 1);
}

int main()
{
    for (int t = 0; t < CASES; t++)
    {
        int n = gen_int(MIN_N, MAX_N);
        int m = std::min(gen_int(MIN_M, MAX_M), n*(n-1)/2);
        printf("%d %d\n", n, m);

        /* Node weights. */
        for (int i = 1; i <= n; i++)
            printf("%d ", gen_int(MIN_V, MAX_V));
        printf("\n");

        /* Edge and weights. */
        std::vector<std::pair<int,int> > pairs;
        pairs.reserve(n*(n-1)/2);
        for (int i = 1; i <= n; i++)
            for (int j = i + 1; j <= n; j++)
                pairs.push_back(std::make_pair(i, j));
        std::random_shuffle(pairs.begin(), pairs.end());

        for (int i = 0; i < m; i++)
        {
            printf("%d %d %d\n", 
                   pairs[i].first, pairs[i].second, gen_int(MIN_V, MAX_V));
        }

        /* Queries. */
        int q = gen_int(MIN_Q, MAX_Q);
        printf("%d\n", q);
        for (int i = 0; i < q; i++)
        {
            int start = gen_int(1, n);
            int end = gen_int(1, n);
            printf("%d %d\n", start, end);
        }
        printf("\n");
    }
    return 0;
}
